#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <omp.h>
#include "mpi.h"

#define  MASTER		      0
#define  NUM_OF_THREADS   100
#define  PRIMO            500041


typedef struct{
    int  contador;   //contador de palavras iguais encontradas no txt
    char word[100];  //armazena as palavras encontradas no txt
}HASH;
//por exemplo: tem 17 palavras "look" no txt.  contador = 17 word = "look"

int hash_code(char *table) {  //funcao que define a posicao no vetor
    int i, h = table[0];

    for (i = 1; table[i] != '\0'; i++)  //for do primeiro caracter ate o espaço, ou seja, ate o fim da palavra
        h = (h * 251 + table[i])%PRIMO; //soma o valor de cada letra para definir uma posicao

    return h; //retorna a posicao no vetor
}

int find_ht(HASH *table, char key[100])  //buscar uma palavra no hash
{
    int i = hash_code(key); //calcula o hash_code da palavra

    if (table[i].word[0] == 0)  //se a posicao do vetor estiver vazia, a busca retorna -1
        return -1;

    if (strcmp(table[i].word, key) == 0) //se a comparacao da palavra buscada com a palavra no vetor for igual a 0 (palavras iguais) retorna a posicao
        return i;

    while(strcmp(table[i].word, key) != 0){ //se a palavra no vetor for diferente da procurada, ir para a proxima posicao do vetor
        i++;
        if(table[i].word[0] == 0 || i >= PRIMO) //se a posicao estiver vazia ou o "i" chegar ao fim do vetor, retorna -1
            return -1;
    }
    return i; //retorna posicao da palavra encontrada
}

int insert_ht(HASH *vet, char word[100])  //insere uma palavra no hash
{
    int pos, i;
    i = find_ht(vet, word); //busca a palavra no hash

    if(i == -1){        //se a palavra nao foi encontrada no hash
        pos = hash_code(word);  //calcula o hash_code da palavra

        while(pos < PRIMO){             //enquanto nao chegar ao fim do vetor
            if(vet[pos].word[0] == 0){  //se a posicao estiver vazia, a palavra vai ser inserida
                strcpy(vet[pos].word, word);    //copia a palavra recebida na posicao do vetor retornada pela funcao "hash_code"
                vet[pos].contador = 1;          //inicia o contador como 1
                break;
            }
            else     //se a posicao nao estiver vazia, vai para a proxima posicao
                pos++;
        }
    }
    else //se foi encontrada
        vet[i].contador++; //incrementa o contador de repeticao da palavra

    return i;
}

HASH *vet1;  //hash onde vao ser armazenadas as palavras com 5 ou menos caracteres
HASH *vet2;  //hash onde vao ser armazenadas as palavras com mais que 5 caracteres

int main(int argc, char *argv[]){

    char c, word[100], p_aleatoria[5], p_aleatoria2[5];
    int	numtasks,              /* number of tasks in partition */
    taskid,                /* a task identifier */
    numworkers,            /* number of worker tasks */
    source,                /* task id of message source */
    dest,                  /* task id of message destination */
    mtype,                  /* message type */
    rc,
    tag1=1, tag2=2, tag3=3, tag4=4, tag5=5, tag6=6, tag7=7,//tags para identificar as mensagens entre os processos
    i, j,                         //incrementos
    n_caracteres_txt, tam_palavra, tam, //tamanhos do txt, tamanha da palavra achada no txt e tamanha da palavra aleatoria gerada
    cont, cont2, cont3, cont_recv, cont_send, soma, //contadores
    pos, fim, tid; //thread ID

    FILE *f;

    /***** Initializations *****/

    MPI_Status    status;
    MPI_Datatype  HASHtype, old_types[2];        //HASHtype é o novo tipo de dado do MPI. "old_types" contem os tipos de dados da struct HASH
    MPI_Aint      int_length, displacements[2];  //int_length vai receber o tamanho de um int. Displacements vai receber o vetor de bytes da HASH
    int           block_length[2];               //recebera os tamanhos das variavies da struct HASH

    rc = MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&taskid);
    MPI_Comm_size(MPI_COMM_WORLD,&numtasks);
    MPI_Type_extent(MPI_INT, &int_length);   //int_length recebe o tamanha de um MPI_INT

    old_types[0] = MPI_INT;  //tipo da variavel hash.contador
    old_types[1] = MPI_CHAR; //tipo da variavel hash.word

    displacements[0] = 0;           //hash.contador encontra-se na posição 0 da HASH
    displacements[1] = int_length;  //hash.word encontra-se depois do hash.contador, ou seja depois do tamanho de bytes de um MPI_INT

    block_length[0] = 1;    //hash.contador tem 1 posicao
    block_length[1] = 100;  //hash.word tem 100 posicoes

    MPI_Type_create_struct(2, block_length, displacements, old_types, &HASHtype); //criando o novo tipo de dado, a partir das informacoes coletadas acima.
                                                                                  //O primeiro parametro é o numero de variaveis da struct e o ultimo é o nome do novo tipo de dado

    MPI_Type_commit(&HASHtype); //certifica a existencia de um novo tipo de dado(HASHtype) perante ao ambiente de execucao do MPI

    if (numtasks < 3){
        printf("Need at least three MPI tasks. Quitting...\n");
        MPI_Abort(MPI_COMM_WORLD, rc);
        exit(1);
    }
    numworkers = numtasks-1;

    /**************************** master task ************************************/
    if (taskid == 0){
        cont = 0;
        cont2 = 0;
        cont3 = 0;
        cont_recv = 0;
        soma = 0;
        tam_palavra = 0;

        vet1 = (HASH*)malloc(PRIMO*sizeof(HASH));
        vet2 = (HASH*)malloc(PRIMO*sizeof(HASH));

        omp_set_num_threads(NUM_OF_THREADS); //define o numero maximo de threads
        #pragma omp parallel for private(i, j) shared(vet1, vet2)
        for(i=0; i<PRIMO; i++){  //zerar todas as posicoes dos vetores
            for(j=0;j<100;j++){
                vet1[i].word[j] = 0;
                vet2[i].word[j] = 0;
            }
            vet1[i].contador = 0;
            vet2[i].contador = 0;
        }

        for(i=0;i<100;i++)
            word[i] = 0;

        f = fopen("palavras.txt", "r");

        fseek(f, 0, SEEK_END); //posiciona o cursor no fim do arquivo

        n_caracteres_txt = ftell(f); //a ultima posicao do arquivo é igual ao numero de caracteres no txt

        fseek(f, 0, SEEK_SET); //posiciona o cursor no inicio do txt

        for(i=0;i<n_caracteres_txt;i++){ //para o primeiro caracter do txt, até o ultimo
            c = fgetc(f); //c recebe o proximo caracter do FILE f

            if((c >= 48 && c <= 57) || (c >= 65 && c<= 90) || (c >= 97 && c<= 122)){ //se o caracter recebido for letra(maiuscula ou minuscula) ou numero
                if((c >= 65 && c<= 90)) //se for maiuscula transforma em minuscula
                    c+=32;
                word[tam_palavra] = c; //adiciona o caracter "c" na palavra word
                tam_palavra++;         //incrementa o tamanho de word
            }
            else if(c == ',' || c == ' ' || c == '-' || c == '\n' || c == '\r'){ //se o caracter recebido for "," ou " " ou "-"  a palavra vai ser inserida na HASH
                if(word[0] != 0){  //se word não for nula. (Tratando o caso de receber, por exemplo, " " seguido de  ","
                    if(tam_palavra <= 5)                //se a palavra tem 5, ou menos caracteres
                        pos = insert_ht(vet1, word);    //insere na hash vet1
                    else                                //se tiver mais que 5
                        pos = insert_ht(vet2, word);    //insere na hash vet2

                    cont++; //incrementa o numero de palavras encontradas no txt

                    for(j=0;j<=tam_palavra;j++) //zerando as posicoes de "word"
                        word[j]=0;
                    tam_palavra=0;
                }
            }
            else if(c == 39) //se o caracter recebido for "'", nada é feito
                continue;
        }
        fclose(f);

        MPI_Send(&vet2[0], PRIMO, HASHtype, 1, tag4, MPI_COMM_WORLD); //envia a hash vet2(que contem as palavras com mais que 5 caracteres do txt) para o processo 1

        for(dest=2;dest<numtasks;dest++)
            MPI_Send(&vet1[0], PRIMO, HASHtype, dest, tag6, MPI_COMM_WORLD);  //envia a hash vet1 para todos os processos

        while(cont2 < 64000){ //enquanto nao forem achadas x palavras
            cont_recv++;    //incrementa o contador de mensagens recebidas
            MPI_Recv(&pos, 1, MPI_INT, MPI_ANY_SOURCE, tag1, MPI_COMM_WORLD, &status);  //recebe de qualquer processo, a posicao de uma palavra gerada aleatoriamente e que foi encontrada na hash

            if(vet1[pos].contador > 0){  //se ainda existem palavras para serem encontradas (palavras repetidas no txt)
                vet1[pos].contador--;    //decrementa o contador
                cont2++;                 //incrementa o contador de palavras com 5 ou menos caracteres encontradas
                printf("%d\n", cont2);
            }
        }

        fim = 1;
        for(dest=2;dest<numtasks;dest++) //para todos os outros processos
            MPI_Send(&fim, 1, MPI_INT, dest, tag2, MPI_COMM_WORLD); //envia fim=1 para finalizarem o processamento

        //antes do master ter enviado o fim, os outros porcessos continuaram enviando mensagens com palavras encontradas, por isso precisamos receber estas mensagens.
        //calculamos o tanto de mensagens enviadas pelo processos e o numero de mensagens recebidas pelo master. Se houver diferença, as mensagens pendentes vao ser
        //recebidas

        for(i=2;i<numtasks;i++){ //para todos os outros processos
            MPI_Recv(&cont_send, 1, MPI_INT, MPI_ANY_SOURCE, tag3, MPI_COMM_WORLD, &status); //o master recebe o cont_send, que representa o numero de mensagem enviadas por cada processo
            soma+=cont_send; //"soma" vai representar o numero de mensagens enviadas por todos os processos para o master, contendo posicoes de palavras encontradas
        }
        soma-=cont_recv; //decrementa de "soma" o numero de mensagens recebidas pelo master de todos os outros processos

        for(i=0;i<soma;i++){
            MPI_Recv(&pos, 1, MPI_INT, MPI_ANY_SOURCE, tag1, MPI_COMM_WORLD, &status); //recebe de qualquer processo, a posicao de uma palavra gerada aleatoriamente e que foi encontrada na hash
            if(vet1[pos].contador > 0){      //se ainda existem palavras para serem encontradas (palavras repetidas no txt)
                    vet1[pos].contador--;    //decrementa o contador
                    cont2++;                 //incrementa o contador de palavras com 5 ou menos caracteres encontradas
                }
        }

        MPI_Send(&fim, 1, MPI_INT, 1, tag7, MPI_COMM_WORLD); //manda o fim para o processo 1, que esta buscando palavras compostas
        MPI_Recv(&cont3, 1, MPI_INT, 1, tag5, MPI_COMM_WORLD, &status); //recebe do processo 1, o numero de palavras compostas encontradas

        MPI_Type_free(&HASHtype);

        free(vet1);
        free(vet2);

        printf("\nTotal de palavras: %d"
               "\nTotal de palavras encontradas: %d"
               "\nTotal de palavras encontradas com 5 ou menos caracteres: %d"
               "\nTotal de palavras encontradas com mais que 5 caracteres: %d"
               "\n%.2f porcento encontradas!\n", cont, cont2+cont3, cont2, cont3, (float)(100*(cont2+cont3))/(float)cont);

    }

    /**************************** worker task ************************************/
    else if(taskid == 1){  //processo que busca as palavras compostas (mais que 5 caracteres)
        cont3=0;
        fim=0;

        vet2 = (HASH*)malloc(PRIMO*sizeof(HASH));

        for(i=0; i<PRIMO; i++){  //zerar todas as posicoes dos vetores
            for(j=0;j<100;j++)
                vet2[i].word[j] = 0;
            vet2[i].contador = 0;
        }

        MPI_Recv(&vet2[0], PRIMO, HASHtype, MASTER, tag4, MPI_COMM_WORLD, &status);   //recebe a hash vet2(que contem as palavras com mais que 5 caracteres do txt)

        omp_set_num_threads(300); //define o numero maximo de threads
        #pragma omp parallel private(i, j, tam, p_aleatoria, p_aleatoria2, word, pos, tid) firstprivate(vet2) shared(fim, cont3)
        for(j=0;j<100000000;j++){  //o for vai até 100 milhoes, mas ele nao roda tudo. Um break interrompe as iteracoes
            tid = omp_get_thread_num(); //cada thread vai receber o seu tid
            if(tid == 0){  //se for a thread 0
                    MPI_Recv(&fim, 1, MPI_INT, MASTER, tag7, MPI_COMM_WORLD, &status);  //fica esperando o MASTER mandar o fim da execucao
                    break;  //finaliza a execucao
            }
            else{
                if(fim == 1)  //se o fim for igual a 1
                    break;   //finaliza a execucao
                for(i=0;i<5;i++){      //zerando os vetores das palavras aleatorias
                    p_aleatoria[i] = 0;
                    p_aleatoria2[i] = 0;
                }
                for(i=0;i<100;i++)  //zerando o vetor da palavra que sera procurada
                    word[i] = 0;

                tam = (rand()%5) + 1;  //gera um numero de 1 a 5 (tamanho da primeira palavra que sera gerada aleatoriamente)
                for(i=0;i<tam;i++)
                    p_aleatoria[i] = 97 + rand()%26;  //gera os caracteres da primeira palavra aleatoriamente

                tam = (rand()%5) + 1;  //gera um numero de 1 a 5 (tamanho da segunda palavra que sera gerada aleatoriamente)
                for(i=0;i<tam;i++)
                    p_aleatoria2[i] = 97 + rand()%26; //gera os caracteres da segunda palavra aleatoriamente

                strcpy(word, p_aleatoria);  //a primeira palavra gerada vai no começo
                strcat(word, p_aleatoria2); //e a segunda vai no fim

                if(strlen(word) <= 5)  //se o resultado dor uma palavra com menos 5 ou menos caracteres, vai para a proxima iteracao, pois estao sendo procuradas palavras com mais que 5 caracteres
                    continue;

                pos = find_ht(vet2, word); //procura na hash vet2

                if(pos != -1){    //se achou na hash
                    if(vet2[pos].contador > 0){ //verifica se o contador esta zerado
                        vet2[pos].contador--;   //se nao estiver, decrementa
                        cont3++;  //contador de palavras encontradas
                    }
                }

                strcpy(word, p_aleatoria2); //agora a segunda palavra gerada vai no começo
                strcat(word, p_aleatoria);  //e a primeira vai no fim

                pos = find_ht(vet2, word);  //procura na hash vet2(que contem as palavras com mais que 5 caracteres do txt)

                if(pos != -1){   //se achou na hash
                    if(vet2[pos].contador > 0){ //verifica se o contador esta zerado
                        vet2[pos].contador--;   //se nao estiver, decrementa
                        cont3++;   //contador de palavras encontradas
                    }
                }
            }
        }
        MPI_Send(&cont3, 1, MPI_INT, MASTER, tag5, MPI_COMM_WORLD);  //manda o contador de palavras encontradas para o MASTER

        free(vet2);
    }

    else if (taskid > 1){  //processos que buscam as palavras simples (ate 5 caracteres)
        fim=0;
        cont_send=0;

        vet1 = (HASH*)malloc(PRIMO*sizeof(HASH));

        for(i=0; i<PRIMO; i++){  //zerar todas as posicoes dos vetores
            for(j=0;j<100;j++)
                vet1[i].word[j] = 0;
            vet1[i].contador = 0;
        }

        MPI_Recv(&vet1[0], PRIMO, HASHtype, MASTER, tag6, MPI_COMM_WORLD, &status); //recebe do master, a hash vet1, que contem as palavras com 5 ou menos caracteres

        omp_set_num_threads(NUM_OF_THREADS); //define o numero maximo de threads
        #pragma omp parallel private(i, p_aleatoria, pos, tam, tid) firstprivate(vet1, tag1, tag2, tag3) shared(cont_send, fim)
        {
            tid = omp_get_thread_num(); //cada thread vai receber o seu tid

            if(tid == 0){ //se for a thread 0
                MPI_Recv(&fim,  1, MPI_INT, MASTER, tag2, MPI_COMM_WORLD, &status); //fica esperando o envio de "fim" pelo master
                sleep(0.5);
                MPI_Send(&cont_send, 1, MPI_INT, MASTER, tag3, MPI_COMM_WORLD);  //envia o cont_send (contador de palavras enviadas) para o master
            }
            else{
                while(fim == 0){ //enquanto o fim nao for mandado pelo master
                    for(i=0;i<5;i++)   //zerando a string da palavra aleatoria
                        p_aleatoria[i] = 0;

                    tam = (rand()%5) + 1; //gera um numero aleatorio entre 1 e 5, que vai ser o tamanha da palavra
                    for(i=0;i<tam;i++)
                        p_aleatoria[i] = 97 + rand()%26;  //gera "tam" caracteres para a palavra aleatoria

                    pos = find_ht(vet1, p_aleatoria);  //busca a palavra gerada na hash. Retorna -1 se a palavra nao for encontrada e a posicao dela na hash se for encontrada

                    if(pos != -1){ //se foi encontrada
                        cont_send++; //incrementa o numero de mensagens enviadas
                        MPI_Send(&pos, 1, MPI_INT, MASTER, tag1, MPI_COMM_WORLD);  //envia a posicao da palavra encontrada para o hash
                    }
                }
            }
        }
        free(vet1);
    }

    MPI_Finalize();  //finaliza o mpi
    return 0;
}

